平面图

置顶 | 发布于 2020-09-05 | 分类于图论、平面图 | 3分钟 | 535字数

一.定义
若能将无向图 $G=(V,E)$ 画在平面上使得任意两条无重合顶点的边不相交，则称 $G$ 是平面图。

在平面图中，由边构成的最小区域称为面，包围该面的边数记为该面的度，特殊的，平面图外的区域也为一个面。

阅读全文 »

网络流24题

置顶 | 发布于 2020-09-05 | 分类于网络流、费用流 | 31分钟 | 5453字数

其实只有 $21$ 道题。两道不是网络流，另一道是假题。

一.最大流问题

1.P2756 飞行员配对方案问题

阅读全文 »

快速傅里叶变换

置顶 | 发布于 2020-09-04 | 分类于多项式、 fft | 27分钟 | 4640字数

一.复数

1.概念

复数就是形如 $a+bi$ 的数，其中 $a,b$ 是实数，且 $b≠0,i^2=- 1$ 。

阅读全文 »

二分图

置顶 | 发布于 2020-07-11 | 分类于二分图、图论 | 9分钟 | 1902字数

一.二分图的基本知识

1.二分图的概念

$~~~~~~~$ 二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集,则称图G为一个二分图。我们一般把其中一部分称为x部，另一部分称为y部。

阅读全文 »

Trie树

置顶 | 发布于 2020-07-11 | 分类于字典树、数据结构、字符串 | 11分钟 | 2216字数

一.引入

如果有一道题是这样的：

给你n个字符串组成的一个词典，m次询问，每次给出一个字符串，问它是否出现在词典中。

阅读全文 »

强连通分量

置顶 | 发布于 2020-07-11 | 分类于图论、强连通分量 | 13分钟 | 2367字数

一.强连通分量的定义

在有向图G中，如果两个顶点vi,vj间（vi！＝vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径（即两点互相可达），则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。

一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

阅读全文 »

回文自动机(PAM)

置顶 | 发布于 2020-07-11 | 分类于回文自动机、字符串 | 6分钟 | 1212字数

一.概念

1.回文自动机

回文自动机，又叫回文树，是一种能在 $\Theta(n)$ 时间玄学解决回文串问题的一种结构，代码难度也十分和蔼可亲。

阅读全文 »

数学杂谈

置顶 | 发布于 2020-07-11 | 分类于数学 | 3分钟 | 479字数

因为没什么好写的，所以这篇博客有点水。

一.调和级数

调和级数即:

阅读全文 »

导数与泰勒公式

置顶 | 发布于 2020-07-11 | 分类于数学 | 13分钟 | 2302字数

前言

此篇文章过于玄学高深，小编这位蒟蒻也不是很懂，所以...

一.导数

阅读全文 »

计算几何

置顶 | 发布于 2020-07-11 | 分类于计算几何、向量 | 9分钟 | 1647字数

本文大部分图片来自网络，侵权删。

一.向量

1.概念

阅读全文 »